#!/usr/env python
#-*-coding: utf-8 -*-

#HEAPSORT(A)
# BUILD-MAX-HEAP(A)
# for i = A.length downto 2
#  exchange A[i] with A[1]
#  A.heap-size = A.heap-size - 1
#  MAX-HEAPFY(a, 1)
#

class HeapSort:
    """ implementação do algoritmo 
    de ordenação heapsort
    """
    
    def __init__(self):
        """Constructor"""
        self.h_size = 0
    pass
    
    #
    # HeapSort algoritm
    # - arrayA, the list of objects to be sorted
    def heap_Sort(self, lstA):
        """Heap-Sort algoritm to  sort a list
        of unsorted objects.
        lstA - list of object to sort
        """
        self.__build_MaxHeap(lstA)
        size = len(lstA) -1
        for i in range(size, 0, -1):
            tmp = lstA[i]
            lstA[i] = lstA[0]
            lstA[0] = tmp
            self.h_size -=1
            self.__max_Heapfy(lstA, 0)
        pass
    pass
    
    # take a lista of objects and create two heap list
    def __max_Heapfy(self, arrayA, pos):
        """maintain the maxHeap property on arrayA[parent(i)] >= arrayA[i]
        for the given list
        arrayA - list of objects to sort
        pos - initial position
        """
        left_s = self.get_leftOf(pos)
        right_s = self.get_rightOf(pos)
        max_pos = 0

        if ((left_s <= (self.h_size -1)) and (arrayA[left_s] > arrayA[pos])):
            max_pos = left_s
        else:
            max_pos = pos
        pass
        
        if ((right_s <= (self.h_size -1)) and (arrayA[right_s] > arrayA[max_pos])):
            max_pos = right_s
            
        if (max_pos != pos):
            tmp = arrayA[pos]
            arrayA[pos] = arrayA[max_pos]
            arrayA[max_pos] = tmp
            
            self.__max_Heapfy(arrayA, max_pos)
        pass
    pass
    
    def __build_MaxHeap(self, arrayA):
        """Building the maxheap for the given list using
        the max_Heapfy functiom
        arrayA - list of object to create the heap over
        """
        size = len(arrayA)
        self.h_size = size
        for k in range(size/2, -1, -1):
            self.__max_Heapfy(arrayA, k)
        pass
    pass
    
    #get the position of the left elemenr
    def get_leftOf(self, a_pos):
        return 2 * a_pos +1
    pass
    
    #get the right elementś position
    def get_rightOf(self, a_pos):
        return 2 * a_pos +2
    pass
pass
